1. Field of the Invention
The present invention relates generally to an apparatus and method for transmitting and receiving data in a communication or broadcasting system, and more particularly, to an apparatus and method for transmitting and receiving data in a communication or broadcasting system using linear block codes.
2. Description of the Related Art
Generally, a communication or broadcasting system transmits and receives data with data generated in an information source of a transmitter wirelessly transmitted over a channel after undergoing source coding, channel coding, interleaving and modulation and a receiver receives the wirelessly transmitted signals, and performs demodulation, deinterleaving, channel decoding and source decoding on the received signals.
In communication or broadcasting systems, signals may be distorted due to channel noises, channel fading, and Inter-Symbol Interference (ISI). Technology for overcoming signal distortion caused by noises, fading and ISI is essential, especially for high-speed digital communication or broadcasting systems requiring high data throughput and high reliability, such as the next-generation mobile communication systems, digital broadcasting systems, and mobile Internet systems. Channel coding and interleaving are typical examples of this technology.
Interleaving is used to distribute the parts where transmission bits are damaged, without concentrating them in one place, so as to minimize the data transmission loss by preventing burst errors that often occur while the data passes through fading channels, and to improve the effects of the channel coding described below.
Channel coding is widely used as a method for increasing reliability of communication by allowing a receiver to check signal distortion caused by the noises, fading and ISI and to recover the signal distortion efficiently. Codes used for channel coding and corrections are called Error-Correcting Codes (ECCs) and research into various types of ECCs has been conducted.
The commonly known linear block codes may include a Low Density Parity Check (LDPC) code. The present invention is described below with reference to the LDPC code, among the linear block codes.
The LDPC code is generally defined as a parity check matrix, and may expressed using a bipartite graph called a Tanner graph. The bipartite graph means that vertices constituting the graph are divided into two different types. The LDPC code is expressed in a bipartite graph including vertexes called variable nodes and check nodes. The variable nodes correspond to coded bits on a one-to-one basis.
Graphical representation of the LDPC code is described below with reference to FIGS. 1 and 2.
FIG. 1 is a diagram illustrating a parity check matrix H1 of an LDPC code, in which the parity check matrix has four rows and eight columns. The matrix in FIG. 1 represents an LDPC code that generates a codeword having a length of 8, as it has eight columns. A relationship between the parity check matrix H1 and an 8-bit codeword c=[c0,c1,c2,c3,c4,c5,c6,c7] is defined as Equation (1) below.H·cT=0c0·h0+c1·h1+c2·h2+c3·h3+c4·h4+c5·h5+c6·h6+c7·h7=0  (1)
In Equation (1), h0, h1, h2, h3, h4, h5, h6, h7 represent columns of the parity check matrix H1, so each column of the parity check matrix may be associated with each codeword bit. That is, an i-th column hi of a parity check matrix is associated with an i-th bit ci of a codeword. Therefore, the number and positions of non-zero entries in each column hi are related to performance of a codeword bit ci.
FIG. 2 is a diagram of a graph representation of a parity check matrix H1 of an LDPC code. Specifically, FIG. 2 is a diagram illustrating a Tanner graph corresponding to the parity check matrix H1 in FIG. 1. Referring to FIG. 2, the Tanner graph of the LDPC code includes eight variable nodes x1 202, x2 204, x3 206, x4 208, x5 210, x6 212, x7 214, and x8 216, and four check nodes 218, 220, 222, and 224. The i-th column and a j-th row of the parity check matrix H1 of the LDPC code correspond to the variable node xi and the j-th check node, respectively. A value of 1 (or a non-zero value) at the point where the i-th column and the j-th row of the parity check matrix H1 of the LDPC code cross each other, means that an edge exists between the variable node xi and the j-th check node on the Tanner graph as illustrated in FIG. 2.
In the Tanner graph of the LDPC code, degrees of variable nodes and check 5 nodes represent the number of edges connected between the nodes, which is the same as the number of non-zero entries in columns or rows corresponding to the associated nodes in the parity check matrix of the LDPC code. For example, in FIG. 2, degrees of the variable nodes x1 202, x2 204, x3 206, x4 208, x5 210, x6 212, x7 214, and x8 216, are 4, 3, 3, 3, 2, 2, 2, and 2, respectively, and degrees of the check nodes 218, 220, 222, and 224 are 6, 5, 5, and 5, respectively. The numbers of non-zero entries in columns of the parity check matrix H1 in FIG. 1, which correspond to the variable nodes in FIG. 2, are equal to the degrees 4, 3, 3, 3, 2, 2, 2, and 2, respectively, and the numbers of non-zero entries in rows of the parity check matrix H1 in FIG. 1, which correspond to the check nodes in FIG. 2, are equal to the degrees 6, 5, 5, and 5, respectively.
As described above, the coded bits are related to columns of the parity check matrix, and correspond to even variable nodes in the Tanner graph on a one-to-one basis. The degrees of the variable nodes, which correspond to the coded bits on a one-to-one basis, are called degrees of the encoded bits.
As to the LDPC code, it is known that codeword bits having higher degrees are superior in decoding performance to codeword bits having lower degrees, because the high-degree variable nodes may acquire more information through iterative decoding, compared with the low-degree variable nodes. However, the performance of codeword bits may not be exactly determined based on only these characteristics. Other characteristics such as cycles of the variable nodes in the Tanner graph, which are mapped to the codeword bits on a one-to-one basis, should be considered.
FIG. 3 is a diagram illustrating a parity check matrix of an LDPC code, having a specific structure. The LDPC code is a code used in Digital Video Broadcasting-Satellite Second Generation (DVB-S2), Digital Video Broadcasting-Second Generation Terrestrial (DVB-T2), and Digital Video Broadcasting-Next Generation Handheld (DVB-NGH), which are European broadcasting systems. The LDPC code has a systematic structure, in which a codeword includes an information word (or an “information part”). Although the LDPC code is described below based on the parity check matrix in FIG. 3 for convenience of description, it is understood by those of ordinary skill in the art that the present invention is not limited to the parity check matrix in FIG. 3, or to DVB-S2, DVB-T2, and DVB-NGH.
Referring to FIG. 3, a parity check matrix includes an information part and a parity part. The information part includes K1 columns, and the parity part includes (N1-K1) columns. The number of rows of the parity check matrix is the same as the number (N1−K1) of columns of the parity part.
N1 represents a length of an LDPC codeword, K1 represents a length of the information part, and (N1−K1) represents a length of the parity part. The “length of a codeword” as used herein may refer to the number of bits constituting the codeword, and the “length of an information part” as used herein may refer to the number of bits constituting the information part. Integers M1 and q are determined to meet q=(N1−K1)/M1, where K1/M1 may also be an integer.
In the parity check matrix illustrated in FIG. 3, positions having a weight of 1 (or weight-1 positions) in K1-th to (N1−1)-th columns corresponding to the parity bits, may form a dual-diagonal structure. Therefore, it is noted that degrees of the columns corresponding to the parity bits, except for the (N1−1)-th column, are all 2, and a degree of the (N1−1)-th column is 1.
Referring to FIG. 3, 0-th to (K1−1) columns corresponding to the information part of the parity check matrix may be generated according to the following rules.
Rule 1: A total of K1/M1 column groups are generated by grouping K1 columns corresponding to the information part of the parity check matrix, by M1. Columns in each column group may be generated according to the following Rule 2.
Rule 2: Positions of 1 in a 0-th column in an i-th column group (i=1, K1/M1) are determined. Assuming that a degree of a 0-th column in each i-th column group is represented by Di and positions of rows with a value of 1 are represented by Ri,0(1), Ri,0(2), . . . , Ri,0(Di), positions Ri,j(k) for (k=1,2, . . . , Di) of rows with a value of 1 in a j-th (j=1, 2, . . . , M1−1) column in an i-th column group may be defined as shown in Equation (2) below:Ri,j(k)=Ri,(j−1)(k)+q mod(N1−K1)k=1,2, . . . ,Di,i=1, . . . ,K1/M1,j=1, . . . ,M1−1  (2)
In accordance with Rules 1 and 2, it is noted that degrees of columns in an i-th column group (i=1, K1/M1) are all constant to Di. A specific example is considered below, for a better understanding of a structure of an LDPC code, which stores information about the parity check matrix according to the above rules.
As a specific example, it is assumed that N1=30, K1=15, M1=5 and q=3, and position information of rows with a value of 1 in 0-th columns in three column groups may be represented in the following sequences. These sequences are referred to as “weight-1 position sequences”.
R1,0(1)=1, R1,0(2)=2, R1,0(3)=8,R1,0(4)=10,
R2,0(1)=0, R2,0(2)=9, R2,0(3)=13,
R3,0(1)=0, R3,0(2)=14.
As for the weight-1 position sequences for the positions of rows with a value of 1 in 0-th columns in column groups, only the sequences for their column groups may be represented as follows, for convenience.
1 2 8 10
0 9 13
0 14
That is, the i-th weight-1 position sequences represent position information of rows with a value of 1 in i-th column groups, respectively.
The LDPC code has been described so far. Signal constellation in a communication or broadcasting system to which a Quadrature Amplitude Modulation (QAM) scheme, the commonly used high-order modulation scheme, is applied, is described below. QAM-modulated symbols are divided into a real part and an imaginary part, and various different modulation symbols may be generated by changing sizes and signs of the real part and the imaginary part. Quadrature Phase Shift Keying (QPSK) modulation scheme is described together, in order to find out the characteristics of QAM.
FIG. 4A is a diagram illustrating a general signal constellation of a QPSK modulation scheme.
Referring to FIG. 4A, y0 determines a sign of the real part and y1 determines a sign of the imaginary part. That is, a sign of the real part is plus (+) for y0=0, and minus (−) for y0=1, and a sign of the imaginary part is plus (+) for y1=0, and minus (−) for y1=1. In the QPSK modulation scheme, (y0, y1) bits corresponding to one modulation signal are the same in reliability because y0 and y1 are the same in error rate as they are sign indication bits representing signs of the real part and the imaginary part. For y0,q and y1,q, the second subscript index q indicates a q-th output of modulation signal-constituting bits.
FIG. 4B is a diagram illustrating a general signal constellation of a 16-QAM modulation scheme.
Referring to FIG. 4B, (y0, y1, y2, y3) bits corresponding to one modulation signal have the following meanings. Bits y0 and y2 determine sign and magnitude of the real part, respectively, and bits y1 and y3 determine sign and magnitude of the imaginary part, respectively. That is, y0 and y1 determine signs of the real part and the imaginary part of the signal, and y2 and y3 determine magnitudes of the real part and the imaginary part of the signal. Because determining signs of the modulation signal is easier than determining magnitudes of the modulation signal, y2 and y3 are higher in error rate than y0 and y1. Therefore, for the (y0, y1, y2, y3) bits, their no-error rates or reliabilities are in order of R(y0)=R(y1)>R(y2)=R(y3). R(y) represents reliability of a bit y. Unlike QPSK modulation signal-constituting bits, QAM modulation signal-constituting bits (y0, y1, y2, y3) are different in reliability.
In the 16-QAM modulation scheme, order and roles of the (y0, y1, y2, y3) bits are subject to change because two bits among the four bits constituting a signal determine signs of the real part and the imaginary part of the signal, and the other two bits determine magnitudes of the real part and the imaginary part of the signal.
FIG. 4C is a diagram illustrating a general signal constellation of a 64-QAM modulation scheme.
Referring to FIG. 4C, among (y0, y1, y2, y3, y4, y5) bits corresponding to one modulation signal, bits y0, y2 and y4 determine sign and magnitude of the real part, and bits y1, y3 and y5 determine sign and magnitude of the imaginary part. The bits y0 and y1 determine signs of the real part and the imaginary part, respectively, and the bits y2 and y3 and the bits y4 and y5 determine magnitudes of the real part and the imaginary part, respectively. Because determining signs of the modulation signal is easier than determining magnitudes of the modulation signal, y0 and y1 are higher in reliability than y2, y3, y4 and y5. The bits y2 and y3 are determined depending on whether a magnitude of the modulated symbol is greater than or less than 4, and the bits y4 and y5 are determined depending on whether a magnitude of the modulated symbol is closer to 4 or 0 from 2, or whether a magnitude of the modulated symbol is closer to 4 or 8 from 6. Therefore, a range for determining y2 and y3 is 4, while a range for determining y4 and y5 is 2. Thus, y2 and y3 are higher than y4 and y5 in reliability. In summary, for the (y0, y1, y2, y3, y4, y5) bits, their no-error rates or reliabilities are in order of R(y0)=R(y1)>R(y2)=R(y3)>R(y4)=R(y5).
In the 64-QAM modulation scheme, among the six bits constituting a signal, two bits determine signs of the real part and the imaginary part of the signal, and four bits determine magnitudes of the real part and the imaginary part of the signal. Therefore, order and roles of the (y0, y1, y2, y3, y4, y5) bits are subject to change.
Although not illustrated in the drawing, even in the signal constellation of a modulation scheme of 256-QAM or more, roles and reliabilities of modulation signal-constituting bits are subject to change in the same manner as described above. That is, for (y0, y1, y2, y3, y4, y5, y6, y7) bits corresponding to one modulation signal, their no-error rates or reliabilities are in order of R(y0)=R(y1)>R(y2)=R(y3)>R(y4)=R(y5)>R(y6)=R(y7).
Conventionally, however, in performing interleaving/deinterleaving, a communication or broadcasting system using an LDPC code uses any interleaving/deinterleaving scheme regardless of the reliability characteristics of the LDPC code or modulation signal-constituting bits of high-order modulation, or uses interleaving/deinterleaving and signal constellation bit-mapping scheme in which only degrees of variable nodes or check nodes of the LDPC code are considered, making it difficult to minimize distortion of signals transmitted over a channel.
One system may use a plurality of parity check matrixes to support a plurality of coding rates. Here, the coding rates have different degree distribution characteristics, so the signal constellation bit-mapping scheme should be different according to the change in the degree distribution characteristic. However, an increase in the number of bit-mapping scheme in use may increase complexity of the system, so there is a need for a method capable of using the same bit-mapping scheme if possible.